//给你一个整数 n ，请你找出并返回第 n 个 丑数 。 
//
// 说明：丑数是只包含质因数 2、3 和/或 5 的正整数；1 是丑数。 
//
// 
//
// 示例 1： 
//
// 
//输入: n = 10
//输出: 12
//解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 
//
// 提示： 
//
// 
// 1 <= n <= 1690 
// 
//
// 
//
// 注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/ 
//
// 
//
// Related Topics 哈希表 数学 动态规划 堆（优先队列） 👍 512 👎 0


package LeetCode.editor.cn;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-05-17 18:50:51
 * @description LCR 168.丑数
 */
public class ChouShuLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ChouShuLcof fun=new ChouShuLcof();
	 	 Solution solution = fun.new Solution();
		solution.nthUglyNumber(10);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //动态规划  时间空间on
    public int nthUglyNumber1(int n) {
		//表示第几个丑数
		int[] dp = new int[n + 1];
		//第一个是1
		dp[1] = 1;
		//初始定义三个指针，表示下一个是这个指针乘上对应的质因数
		int p2 = 1, p3 = 1, p5 = 1;
		for (int i = 2; i <= n; i++) {
			int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
			//dp[i]由 三个指针中的最小值贡献，这样能保证丑数是顺序的
			dp[i] = Math.min(Math.min(num2, num3), num5);
			//依次检查是由哪个贡献的，对应的指针向前，同时例如6，可能是2和3同时贡献的，因此不用else，都用if
			if (dp[i] == num2) {
				p2++;
			}
			if (dp[i] == num3) {
				p3++;
			}
			if (dp[i] == num5) {
				p5++;
			}
		}
		return dp[n];

    }
	//优先队列，空间on 时间 onlogn
	public int nthUglyNumber(int n) {
		int[] factors = {2, 3, 5};
		Set<Long> seen = new HashSet<Long>();
		PriorityQueue<Long> heap = new PriorityQueue<Long>();
		seen.add(1L);
		heap.offer(1L);
		int ugly = 0;
		//因为丑数的因数都是丑数
		//把2x 3x 5x都入堆，每次都是按顺序存的，所以第n次就是第n大的丑数
		//但是这样会存入多余的丑数
		for (int i = 0; i < n; i++) {
			long curr = heap.poll();
			ugly = (int) curr;
			for (int factor : factors) {
				long next = curr * factor;
				if (seen.add(next)) {
					heap.offer(next);
				}
			}
		}
		return ugly;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
